#include <stdio.h>

#define True 1
#define False 0
#define MaxSize 100

char adj[ MaxSize ][ MaxSize ];
int x[ MaxSize ];
long count_iter;

int ham( int ), ok( int, int );

void main()
{
   char filename[ FILENAME_MAX ];
   int n = 0, i, j, v1, v2, ans;
   FILE *fp;

   for ( ;; ) {
      printf( "\n\nDo another (1 = yes, 0 = no)? " );
      scanf( "%d", &ans );
      if ( !ans )
         break;
      printf( "Which file? " );
      scanf( "%s", filename );
      if ( ( fp = fopen( filename, "r" ) ) == NULL )
         printf( "Can't open file %s\n", filename );
      else {
         for ( i = 1; i <= n; i++ )
            for ( j = 1; j <= n; j++ )
               adj[ i ][ j ] = False;
         fscanf( fp, "%d%d", &n, &ans );
         while ( fscanf( fp, "%d%d%d", &v1, &v2, &ans ) != EOF )
            adj[ v1 ][ v2 ] = adj[ v2 ][ v1 ] = True;
         count_iter = 0;
         if ( ham( n ) ) {
            printf( "Graph has a Hamiltonian cycle\n"
                    "Hamiltonian cycle:\n\t" );
            for ( i = 1; i <= n; i++ )
               printf( "%d ", x[ i ] );
            putchar( '\n' );
         }
         else
            printf( "Graph has no Hamiltonian cycle\n" );
      }
   }
}


int ham( int n )
{
   int k, resp;

   x[ 1 ] = x[ 2 ] = 1;
   k = 2;

   while ( k > 1 ) {
      count_iter++;
      if ( count_iter % 10000 == 0 ) {
         printf( "\n%ld iterations. Continue (1 = yes, 0 = no)? ", 
                 count_iter );
         scanf( "%d", &resp );
         if ( !resp )
            return False;
      }
      do {
         x[ k ]++;
      } while ( x[ k ] <= n && !ok( k, n ) );
      if ( x[ k ] <= n ) {
         if ( k == n )
            return True;
         k++;
         x[ k ] = 1;
      }
      else
         k--;
   }

   return False;
}

int ok( int k, int n )
{
   int i;

   for ( i = 1; i <= k - 1; i++ )
      if ( x[ i ] == x[ k ] )
         return False;
   if ( k < n )
      return adj[ x[ k - 1 ] ][ x[ k ] ];
   else
      return adj[ x[ n - 1 ] ][ x[ n ] ] && adj[ x[ 1 ] ][ x[ n ] ];
}